package com.learn.medium;

import java.util.Arrays;
import java.util.HashMap;

/**
 * Let the function f(s) be the frequency of the lexicographically <b>smallest character</b> in a non-empty string s.<br>
 * For example, if s = "dcce" then f(s) = 2 because the lexicographically smallest character is 'c', which has a frequency of 2.<br>
 * You are given an array of strings words and another array of query strings queries. For each query queries[i],<br>
 * count the number of words in words such that f(queries[i]) < f(W) for each W in words.<br>
 * Return an integer array answer, where each answer[i] is the answer to the ith query.<br>
 * Example 1:<br>
 * Input: queries = ["cbd"], words = ["zaaaz"]<br>
 * Output: [1]<br>
 * Explanation: On the first query we have f("cbd") = 1, f("zaaaz") = 3 so f("cbd") < f("zaaaz").<br>
 * Example 2:<br>
 * Input: queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]<br> Output: [1,2]<br>
 * Explanation: On the first query only f("bbb") < f("aaaa"). On the second query both f("aaa") and f("aaaa") are both > f("cc").
 */
public class num_1170 {
    public static void main(String[] args) {
        String[] queries = { "bba", "abaaaaaa", "aaaaaa", "bbabbabaab", "aba", "aa", "baab", "bbbbbb", "aab",
                "bbabbaabb" };
        String[] words = { "aaabbb", "aab", "babbab", "babbbb", "b", "bbbbbbbbab", "a", "bbbbbbbbbb", "baaabbaab",
                "aa" };

        System.out.println(Arrays.toString(numSmallerByFrequency(queries, words)));
    }

    public static int[] numSmallerByFrequency(String[] queries, String[] words) {
        if (queries == null || queries.length == 0) {
            return new int[0];
        }
        int[] ret = new int[queries.length];
        int[] queCount = new int[queries.length];
        int[] wordsCount = new int[words.length];
        for (int i = 0; i < queries.length; i++) {
            queCount[i] = getCharMaxOccur(queries[i]);
        }
        for (int i = 0; i < words.length; i++) {
            wordsCount[i] = getCharMaxOccur(words[i]);
        }
        Arrays.sort(wordsCount);
        for (int i = 0; i < queries.length; i++) {
            int l = 0;
            int r = words.length;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (queCount[i] < wordsCount[mid]) {
                    r = mid;
                } else {
                    l = mid+1;
                }
            }
            ret[i] = words.length - l;
        }
        return ret;
    }

    private static int getCharMaxOccur(String s) {
        int maxCount = 0;
        String tmpStr = s;
        char tmpChar = 999;
        while (tmpStr.length() > 0) {
            char strChar = tmpStr.charAt(0);
            String tmp = tmpStr.replaceAll(String.valueOf(strChar), "");
            if (tmpChar > strChar) {
                maxCount = tmpStr.length() - tmp.length();
                tmpChar = strChar;
            }
            tmpStr = tmp;
        }
        return maxCount;
    }

    //version-1
    // int[] count = new int[queries.length];
    // int gtCount = 0;
    // int loc = 0;
    //     for (String query : queries) {
    //     int charMaxOccur = getCharMaxOccur(query);
    //     for (String word : words) {
    //         int tmpCount = getCharMaxOccur(word);
    //         if (tmpCount > charMaxOccur) {
    //             gtCount++;
    //         }
    //     }
    //     count[loc] = gtCount;
    //     gtCount = 0;
    //     loc++;
    // }
    //     return count;

}
